package com.Leetcode;

import com.Util.ProduceTree;
import com.structure.TreeNode;

public class Index106BuildTree {
	public static void main(String[] args) {
		int[] inorder = {9,3,15,20,7}, postorder = {9,15,7,20,3};
		Index106BuildTree build = new Index106BuildTree();
		TreeNode root = build.buildTree(postorder, inorder);
		System.out.println(ProduceTree.treeNodeToString(root));
	}
	
	public TreeNode buildTree(int[] postorder, int[] inorder) {
		TreeNode root = buildBinaryTree(postorder,inorder,0,postorder.length-1,postorder.length-1);
		return root;
    }
	
	TreeNode buildBinaryTree(int[] postorder,int[] inorder,int low,int high,int index){
		if(high < low) return null;
		TreeNode node = new TreeNode(postorder[index]);
		int pos = low;
		for(int i = low;i <= high; i ++)
			if(inorder[i] == postorder[index]) {
				pos = i;
			}
		node.left = buildBinaryTree(postorder,inorder,low,pos-1,index-(high-pos)-1);
		node.right = buildBinaryTree(postorder,inorder,pos+1,high,index-1);
		return node;
    }
}
